Distributed data-storage systems (“DSSs”) are complex software solutions that operate over hardware infrastructures consisting of a large number of servers of various designations that are connected together by multiple communication channels. Existing DSSs are subject to various kinds of hardware failures, including total or partial switching off of the electrical supply, network failures that may result in the DSS being divided into separate unconnected segments, disk failures, and the like.
Conventionally, there are two main approaches to ensuring reliability of data storage in conditions of failure, based on the duplication of information and the spreading of data over different components of the distributed data-storage system. The first approach is data replication and the second approach is erasure coding.
In general, data replication is the storage of each block of data (i.e., file or object, depending on the architecture of the data-storage system) in several copies on different disks or different nodes of the system. As a result, replication makes it possible to ensure maximum efficiency of data access, including a significant increase in speed of read access to data frequently used by different clients. However, data replication can be very costly from the perspective of the amount of disk space needed to create the several copies of each block of data.
The more popular backup technique is erasure (or redundant) coding, which is based on the use of mathematical algorithms to generate n chunks (i.e., data fragments or “derivatives”) of a block of data using compression techniques in such a way that any k chunks will be sufficient to recover the initial block of data. Each of the n chunks obtained should be written to a separate disk, and, preferably, to a separate server to ensure high availability of the data. The reliability of a scheme of noiseless coding with parameters n,k (i.e., an “(n,k) scheme”) is comparable to the reliability with replication of data with n−k+1 copies of each data block.
The use of noiseless coding makes it possible to reduce considerably the overheads on data storage necessary for data replication—the redundancy of data storage (i.e., including the ratio of the volume of storable data to the volume of useful data) for an (n,k) scheme is equal to n/k (the size of a data chunk is approximately equal to SizeBlock/k, where SizeBlock is the volume of the initial block of data). The most widely used error-correcting codes in modern software systems of data storage are Reed-Solomon codes and variations, such as Cauchy codes, for example.
In these fault tolerant storage systems, usually any data fragment is split into k+m chunks, where k are the data chunks and m is the number of chunks generated on the basis of data chunks. For the generation, the error-correcting codes, such as the Reed-Solomon codes, allow the system to avoid primitive data duplication, but provide a very reliable mechanism that helps to restore all data even if some disks or servers become damaged. For example, to restore any k data chunks, the system should store k+m chunks. If any m chunks are lost, the system can completely restore all the data with remaining k chunks and it does not matter if they are data chunks or generated chunks.
FIG. 1 illustrates a flow diagram of the data storage technique using a conventional erasure coding algorithm. As shown, K data blocks 20 (i.e., data blocks 11-15) can be created from data fragment 10 using different algorithms (for example, using Reed-Solomon code). Moreover, M parity blocks 30 (i.e., data blocks 16-17) can be generated on the basis of the initial data blocks K. In case the DSS suffers any loss of any data block K, data can be recovered using the number of parity blocks M. Moreover, the number of parity blocks M can be selected depending on the desired degree of redundancy of the storage.
While data storage using erasure coding algorithms can be quite efficient, any excess storage is still associated with significant costs to the distributed storage system. In particular, redundancy requires additional storage devices and data centers. Moreover, data centers are constantly faced with the lack of storage space because the volume of data always grows faster than the capacity of the data storage.
In addition, reliable fault-tolerant storage systems should preferably use distributed data storage in that different data blocks and parity blocks should be stored on different servers to reduce the chance of data loss in case on or more servers fails, for example. Accordingly, increasing the number of storage servers will necessarily improve storage reliability.
Thus, a system and method is needed to enable distributed storage systems and service providers to support the integrity of data storage by increasing the number of storage servers.